package course.p7_binaryTree.s4_AVLTree;

import course.p7_binaryTree.Node;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 平衡二叉搜索树
 * 在BSTree的基础上再加上下面的限制条件：
 * 每个左右子树的高度差保持不大于1
 *
 * 也就是说，在插入，删除操作的时候，我们需要做一些操作保持每个左右子树的高度差不大于1，这个操作称之为旋转
 * 其中心思想是：
 * 将从插入点到根节点路径上第一个不满足AVL性质的节点修复
 */
public class AVLTree {


    int Height(Node root) {
        if(root == null)
            return -1;
        else
            return root.getHeight();
    }


    /**
     * 在节点的左孩子的左子树插入
     * 右旋操作,操作步骤是：
     * 首先得到root的左孩子left
     * 然后将root的左孩子设置left的右孩子
     * 然后将left的右孩子设置为root
     * @param root
     * @return
     */
    Node SingleRotataLeft(Node root) {
        // 得到root的左节点
        Node left = root.getLeft();
        // 将root的左子树设置为left的右子树
        root.setLeft(left.getRight());
        // 将left的右节点设为root
        left.setRight(root);
        // 维护root和left的高度
        root.setHeight(Math.max(Height(root.getLeft()),Height(root.getRight()))+1);
        left.setHeight(Math.max(Height(left.getLeft()),Height(left.getRight()))+1);

        return left;
    }


    /**
     * 在右孩子的右子树插入元素
     * 左旋操作,操作步骤是：
     * 首先得到root的右孩子right
     * 然后将root的右孩子设置为right的左孩子
     * 最后将right的左孩子设置为root
     * @param root
     * @return
     */
    Node SingleRotataRight(Node root) {

        Node right = root.getRight();
        root.setRight(right.getLeft());
        right.setLeft(root);

        root.setHeight(Math.max(Height(root.getRight()),Height(root.getLeft()))+1);
        right.setHeight(Math.max(Height(right.getRight()),Height(right.getLeft()))+1);

        return right;
    }

    /**
     * 在左孩子的右子树插入元素
     * 先将左孩子节点整体向左旋转，然后将root整体向右旋转
     * @param root
     * @return
     */
    Node DoubleRotatewithLeft(Node root) {
        root.setLeft(SingleRotataRight(root.getLeft()));
        return SingleRotataLeft(root);
    }


    /**
     * 在右孩子的左子树插入元素
     * 先将左孩子节点整体向右旋转，然后将root整体向左旋转
     * @param root
     * @return
     */
    Node DoubleRotatewithRight(Node root) {
        root.setRight(SingleRotataLeft(root.getRight()));
        return SingleRotataRight(root);
    }




    /**
     * 平衡二叉搜索树的插入操作
     * @param root 根节点
     * @param data 插入的数据
     * @return
     */
    Node insert(Node root,int data) {
        // root为叶子节点时，直接插入
        if(root == null) {
            root = new Node();
            root.setData(data);
            root.setHeight(0);
            root.setLeft(null);
            root.setRight(null);
        }
        // 向左子树插入
        else if(data < root.getData()) {
            root.setLeft(insert(root.getLeft(),data));
            // 检查左右子树树高进行修正
            if(Height(root.getLeft())-Height(root.getRight())>1) {
                // 左左插入,进行右旋操作
                if(data < root.getLeft().getData())
                    root = SingleRotataLeft(root);
                // 左右插入, 进行双旋操作
                else
                    root = DoubleRotatewithLeft(root);
            }
        }
        // 向右子树插入
        else if(data > root.getData()) {
            root.setRight(insert(root.getRight(),data));
            // 检查左右子树树高进行修正
            if(Height(root.getRight())-Height(root.getLeft())>1){
                // 右右插入，进行左旋
                if(data > root.getRight().getData())
                    root = SingleRotataRight(root);
                // 右左插入，双旋操作
                else
                    root = DoubleRotatewithRight(root);
            }
        }
        root.setHeight(Math.max(Height(root.getLeft()),Height(root.getRight()))+1);
        return root;
    }

    /**
     * 计算指定树root的深度
     * @param root 树的根节点
     * @param deep 树的初始深度
     * @param max 存储该树的深度
     */
    public void getDeep(Node root, Integer deep, int[] max) {
        if(root!=null) {
            deep = deep + 1;
            getDeep(root.getLeft(),deep,max);
            getDeep(root.getRight(),deep,max);
            if(deep > max[0]) max[0] = deep;
        }
    }

    /**
     * 返回目标节点,查找效率高，相当于二分查找
     * @param root 二叉树根节点
     * @param data 要寻找的数据
     * @return 值等于data的节点
     */
    Node find(Node root,int data) {
        if(root==null) return null;
        while (root!=null) {
            if(data==root.getData())
                return root;
            else if(data > root.getData())
                root = root.getRight();
            else root = root.getLeft();
        }
        return null;
    }

    /**
     * 寻找树中最小元素
     * 基本思想是此树的最小元素一定在最左边
     * @param root
     * @return
     */
    Node findMin(Node root) {
        if(root==null) return null;
        while(root.getLeft()!=null)
            root = root.getLeft();
        return root;
    }

    /**
     * 寻找树中最大元素
     * 基本思想是此树的最大元素一定在最右边
     * @param root
     * @return
     */
    Node findMax(Node root) {
        if(root==null) return null;
        while(root.getRight()!=null)
            root = root.getRight();
        return root;
    }


    /**
     * 中序遍历
     * @param first
     */
    void Check3(Node first) {
        if(first!=null) {
            Check3(first.getLeft());
            System.out.print(first.getData()+" ");
            Check3((first.getRight()));
        }
    }

    /**
     * 将层次遍历的结果存入二维数组中
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder(Node root) {
        Queue<Node> queue= new LinkedList<>();
        List<List<Integer>> result = new ArrayList<>();
        if(root!=null) queue.add(root);
        while(!queue.isEmpty()) {
            List<Integer> temp = new ArrayList<>();
            int size = queue.size();
            for(int i=0;i<size;i++) {
                Node node = queue.poll();
                assert node != null;
                temp.add(node.getData());
                if(node.getLeft()!=null) queue.add(node.getLeft());
                if(node.getRight()!=null) queue.add(node.getRight());
            }
            result.add(temp);
        }
        return result;
    }



}
